package _17_graph;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author: mornd
 * @dateTime: 2023/6/25 - 21:27
 * 多源最短路径算法
 *
 * 该算法以其发明者的名字命名，即Robert Floyd和Stephen Warshall。
 * 它使用动态规划的思想，通过对图中所有节点之间的中间节点进行遍历和比较，逐步更新节点之间的最短路径长度。
 */
public class FloydWarshall {

    @Test
    public void test() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");

        // 参照图片 img/floydwarshall.png
        v1.edges = List.of(new Edge(v3, -2));
        v3.edges = List.of(new Edge(v4, 2));
        v4.edges = List.of(new Edge(v2, -1));
        v2.edges = List.of(new Edge(v1, 4), new Edge(v3, 3));

        List<Vertex> graph = List.of(v1, v2, v3, v4);

        floydWarshall(graph);
    }

    private void floydWarshall(List<Vertex> graph) {
        int size = graph.size();
        int[][] dist = new int[size][size];
        // 来自
        Vertex[][] prev = new Vertex[size][size];

        // 1、填充数据
        for (int i = 0; i < size; i++) {
            Vertex v = graph.get(i);

            // 转为 map 提高查找效率
            Map<Vertex, Integer> map = v.edges.stream()
                    .collect(Collectors.toMap(e -> e.linked, e -> e.weight));

            for (int j = 0; j < size; j++) {
                Vertex u = graph.get(j);
                if (v == u) {
                    // 自己通往自己
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = map.getOrDefault(u, Integer.MAX_VALUE);
                    prev[i][j] = map.containsKey(u) ? v : null;
                }
            }
        }
//        print(dist);

        // 2、借路
        for (int k = 0; k < size; k++) {
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    // k=借助的顶点 i=行 j=列
                    // dist[i][k] + dist[k][j] 借助其它顶点(k)到达的距离
                    // dist[i][j] 直接到达的距离

                    // dist[i][k] != Integer.MAX_VALUE 表示i，k这条路走不通
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
                            && dist[i][k] + dist[k][j] < dist[i][j]) {
                        // 如果借助其它顶点到达的距离小于直接到达的距离，那么就更新
                        dist[i][j] = dist[i][k] + dist[k][j];
                        prev[i][j] = prev[k][j];
                    }
                }
            }
            print(dist);
        }

        // 从哪里而来
//        printVertex(prev);

        // 打印路径
//        for (int i = 0; i < size; i++) {
//            for (int j = 0; j < size; j++) {
//                path(prev, graph, i, j);
//            }
//        }

        // 是否存在负环
//        System.out.println(hasNegativeCycle(dist));
    }

    // 打印二维表格内容
    private void print(int[][] dist) {
        System.out.println("-------------------------");
        for (int[] row : dist) {
            String result = Arrays.stream(row).boxed()
                    .map(x -> x == Integer.MAX_VALUE ? "∞" : String.valueOf(x))
                    .map(s -> String.format("%2s", s))
                    .collect(Collectors.joining(",", "[", "]"));
            System.out.println(result);
        }
    }

    private void printVertex(Vertex[][] prev) {
        System.out.println("-----------------------------");
        for (Vertex[] row : prev) {
            System.out.println(Arrays.stream(row).map(v -> v == null ? "null" : v.name)
                    .map(s -> String.format("%5s", s))
                    .collect(Collectors.joining(",", "[", "]")));
        }
    }

    /*
        [v1,v2] [v1, v3, v4, v2]  // v1到v2  途中需要经过 v3、v4
        [v1,v4] [v1, v3, v4]   // v1到v4  途中需要经过 v3
     */
    private void path(Vertex[][] prev, List<Vertex> graph, int i, int j) {
        LinkedList<String> stack = new LinkedList<>();
        System.out.print("[" + graph.get(i).name + "," + graph.get(j).name + "] ");
        stack.push(graph.get(j).name);
        while (i != j) {
            Vertex p = prev[i][j];
            stack.push(p.name);
            j = graph.indexOf(p);
        }
        System.out.println(stack);
    }

    /**
     * 检测是否存在负环
     *
     * @param dist
     * @return
     */
    public boolean hasNegativeCycle(int[][] dist) {
        // 检查是否存在负环
        for (int i = 0; i < dist.length; i++) {
            if (dist[i][i] < 0) {
                return true;
            }
        }
        return false;
    }
}
